//
//  Problem21.swift
//  LeetCode - 21 - 合并两个有序链表
//
//  Created by 毕武侠 on 2020/7/4.
//  Copyright © 2020 毕武侠. All rights reserved.
//

import UIKit
/*
 【21  合并两个有序链表】
 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 
 示例：
 输入：1->2->4, 1->3->4
 输出：1->1->2->3->4->4

 */
/**
 * Definition for singly-linked list.
 */
public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init() { self.val = 0; self.next = nil; }
    public init(_ val: Int) { self.val = val; self.next = nil; }
    public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
}

// 创建list
func createList(_ array: [Int]) -> ListNode? {
    let head = ListNode(0)
    var list: ListNode? = head
    for num in array {
        let node = ListNode(num)
        list?.next = node
        list = list?.next
    }
    return head.next
}

// 打印Node
func printNode(_ l: ListNode?) -> String {
    var string = ""
    var node = l
    while node != nil {
        string = string.appending(String( node!.val))
        string = string.appending(" -> ")
        node = node?.next
    }
    print(string)
    return string
}

class Problem21: NSObject {
    
    func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        if l1 == nil {
            return l2
        } else if l2 == nil {
            return l1
        } else if l1!.val < l2!.val {
            l1?.next = mergeTwoLists(l1?.next, l2)
            return l1
        } else {
            l2?.next = mergeTwoLists(l1, l2?.next)
            return l2
        }			
    }

}
